- Title
- Degree sequences and poset structure of order 9 graphs
- Creator
- Adams, Peter; Eggleton, Roger B.; MacDougall, James A.
- Relation
- Congressus Numerantium Vol. 166, p. 83-95
- Publisher
- Utilitas Mathematica Publishing Inc
- Resource Type
- journal article
- Date
- 2004
- Description
- The set G(n) of unlabelled simple graphs of order n is a poset with partial ordering G ≤ H whenever G is a spanning subgraph of H. On the website www.maths.uq.edu.au/~pa/research/poset9.html we have made available a tabulation of the Hasse diagram for G(9), a digraph of order 274668 and size 4147388, extending our recent tabulations for G(n) with 4 ≤ n ≤ 8. The present paper is a descriptive summary of features of G(9) derived from the tabulation, including: the maximum number of graphs in G(9) with the same degree sequence is 3020, corresponding to 2¹3²4³5²6¹; there are 36 self-complementary graphs in G(9), but 10794 graphs with self-complementary degree sequences; there are 49 graphs in G(9) that are edge-transitive, and 134996 that have no edge-symmetry; the maximum number of immediate successors of a graph in G(9) is 28, and 12 graphs attain this maximum; the number of immediate successors of a graph in G(9) is distributed unimodally, with peak at 16 attained by 25010 graphs. All underlying data are available on the website.
- Subject
- 05C99; 05C07; 06A07; degree sequences; poset structure
- Identifier
- http://hdl.handle.net/1959.13/803792
- Identifier
- uon:6509
- Identifier
- ISSN:0384-9864
- Language
- eng
- Reviewed
- Hits: 15073
- Visitors: 16124
- Downloads: 5
| Thumbnail | File | Description | Size | Format |
|---|